package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/9/1.<br><br>
 *
 * 中等：颜色分类
 */
public class Topic75 {

    public static void main(String[] args) {
        Topic75 instance = new Topic75();

        int[] array = new int[] {2,0,2,1,1,0};
        instance.sortColors(array);
        Util.printArray(array);

        array = new int[] {2,0,1};
        instance.sortColors(array);
        Util.printArray(array);

        array = new int[] {0};
        instance.sortColors(array);
        Util.printArray(array);

        array = new int[] {1};
        instance.sortColors(array);
        Util.printArray(array);

        array = new int[] {2,1,2};
        instance.sortColors(array);
        Util.printArray(array);
    }

    public void sortColors(int[] nums) {
        if(nums.length < 2) {
            return ;
        }

        int ptr0 = 0;
        int ptr2 = nums.length - 1;

        for(int i = 0; i <= ptr2; i++) {
            while (i <= ptr2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[ptr2];
                nums[ptr2] = temp;
                ptr2--;
            }

            if(nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr0];
                nums[ptr0] = temp;
                ptr0++;
            }
        }
    }

    public void sortColors3(int[] nums) {
        if(nums.length < 2) {
            return ;
        }

        int ptr = 0;

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ptr++;
            }
        }

        for(int i = ptr; i < nums.length; i++) {
            if(nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ptr++;
            }
        }
    }

    public void sortColors2(int[] nums) {
        if(nums.length < 2) {
            return ;
        }

        int zero = 0;
        int one = 0;

        for(int value : nums) {
            if(value == 0) {
                zero++;
            }
            else if(value == 1) {
                one++;
            }
        }

        for(int i = 0; i < nums.length; i++) {
            if(i < zero) {
                nums[i] = 0;
            }
            else if(i < zero + one) {
                nums[i] = 1;
            }
            else {
                nums[i] = 2;
            }
        }
    }
}
